home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / ladderbl.txt < prev    next >
Text File  |  1995-11-30  |  4KB  |  140 lines
  1.                 Large Block DES Newsletter
  2.  
  3.                       Vol. I, No. 1
  4.                       Feb. 28, 1994
  5.  
  6.                     Terry Ritter, Ed.
  7.  
  8.  
  9.  
  10.  Current Standings for the Large-Block DES Proposals:
  11.  
  12.  
  13.  I. NxM DES:
  14.  
  15.              A             B
  16.              v             v
  17.       k1 -> DES1    k2 -> DES2
  18.              v             v
  19.              C             D
  20.           Exchange Right 4 Bytes
  21.              E             F
  22.              v             v
  23.       k3 -> DES3    k4 -> DES4
  24.              v             v
  25.              G             H
  26.  
  27.       Falls to meet-in-the-middle like double-DES.  Falls to a
  28.       practical attack by Biham, now called "fix-in-the-middle."
  29.  
  30.  
  31.  II.  NxM DES Found Weak
  32.  
  33.       Announcement of above.
  34.  
  35.  
  36.  III.  Isolated Double-DES
  37.  
  38.       2x construct found weak in original article.
  39.  
  40.       The 1x construct:
  41.  
  42.             A
  43.             v
  44.      k1 -> DES1
  45.             v
  46.             B
  47.             v
  48.      km -> XOR
  49.             v
  50.             C
  51.             v
  52.      k2 -> DES2
  53.             v
  54.             D
  55.  
  56.       was found weak by Chris Dodd <dodd@csl.sri.com> who pointed
  57.       out that two different blocks of known-plaintext (A,D) and
  58.       (A',D') will allow matching (B XOR B') and (C xor X').  (This
  59.       is similar to Biham's "fix-in-the-middle.")  Good going Chris!
  60.  
  61.       Also found by Stefan Lucks <lucks@namu01.gwdg.de>.
  62.  
  63.  
  64.  IV. Ladder-DES
  65.  
  66.              A              B
  67.              |      k1      |
  68.              v      v       |
  69.             XOR <- DES1-----|
  70.              |              |
  71.              |      k2      |
  72.              |      v       v
  73.              |---- DES2 -> XOR
  74.              |              |
  75.              |      k3      |
  76.              v      v       |
  77.             XOR <- DES3 ----|
  78.              |              |
  79.              |      k4      |
  80.              |      v       v
  81.              |---- DES4 -> XOR
  82.              |              |
  83.              v              v
  84.              C              D
  85.  
  86.       Joseph C. Konczal <jkonczal@nist.gov> points out that the
  87.       construct is indeed vulnerable to meet-in-the-middle.  I
  88.       agree, but note that this seems to imply a 112-bit search.
  89.       Since we don't need more than 112 or 120 bits of strength,
  90.       I don't see it as a problem.  (Indeed, if we could get more
  91.       strength, we might want to trade it for speed anyway.)  112
  92.       bits (or so) is the design goal, which should be enough for
  93.       a couple of decades.
  94.  
  95.       In a normal cipher design, I would expect each key bit to
  96.       contribute toward strength, but these are hardly normal cipher
  97.       designs.  Especially when we try to expand block size, extra
  98.       keys may simply provide another small block with the same
  99.       strength as a previous small block.  Keys will be delivered
  100.       electronically, so the relatively rare delivery of 2x or 4x
  101.       or even 8x the expected key material should not pose a serious
  102.       problem.
  103.  
  104.  
  105.       However, Biham reports:
  106.  
  107.            "ladder DES is not more secure than 2**88 steps and
  108.            2**64 chosen plaintexts."
  109.  
  110.       Now, 2^88 cipherings is 2^32 times as strong as the 2^56
  111.       currently in DES (and larger than Skipjack), but hardly the
  112.       2^112 intended.  For the current design the current options
  113.       are:
  114.  
  115.          1) live with the 2^88 strength (so far!),
  116.          2) design the rest of the system to prevent chosen
  117.             plaintexts, or
  118.          3) prevent more than, say, 2^32 block cipherings under a
  119.             single key.
  120.  
  121.       Actually, we need to know exactly what the problem is, and the
  122.       limits of it, before we can propose a fix, or decide whether
  123.       the ladder-DES scheme is unfixable.
  124.  
  125.  
  126.  Summary
  127.  
  128.  Three substantially different constructs proposed; of these, two
  129.  fall, and one is wounded.
  130.  
  131.  To review, the intent is to find some relatively-simple construct
  132.  which builds on the assumed strength of DES to deliver wide blocks
  133.  and something like 112 bits of strength, with less processing than
  134.  triple-DES.  (I see no need for super-strength, unless it is free.)
  135.  
  136.  We still do not know whether or not this is possible.
  137.  
  138.  
  139.  
  140.